package com.leetcode;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;

@Slf4j
public class LeetCode15 {
    //这个超时了
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 3) {
            return res;
        }
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int va = -(nums[i] + nums[j]);
                for (int k = 0; k < nums.length; k++) {
                    if (nums[k] == va && k != i && k != j) {
                        Integer[] aa = {nums[i], nums[j], nums[k]};
                        Arrays.sort(aa);
                        res.add(Arrays.asList(aa));
                    }
                }
            }
        }

        return res.stream().distinct().collect(Collectors.toList());
    }

    // 这个也超时了
    public List<List<Integer>> threeSum1(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 3) {
            return res;
        }
        for (int l = 0; l < nums.length; l++) {
            int num = nums[l];
            for (int i = l + 1; i < nums.length; i++) {
                int num1 = nums[i];
                for (int j = i + 1; j < nums.length; j++) {
                    int num2 = nums[j];
                    if (i != j && l != j && num1 + num2 + num == 0) {
                        Integer[] s = {num, num1, num2};
                        res.add(Arrays.asList(s));
                    }
                }
            }
        }

        return res.stream().distinct().collect(Collectors.toList());
    }


    public List<List<Integer>> threeSum2(int[] nums) {
        Arrays.sort(nums);
        Map<Integer,List<Integer>> res = new HashMap<>();
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int va = -(nums[i] + nums[j]);
                for (int k = 0; k < nums.length; k++) {
                    if (nums[k] == va && k != i && k != j) {
                        Integer[] aa = {nums[i], nums[j], nums[k]};
                        Arrays.sort(aa);
                        res.put(i+j+k,Arrays.asList(aa));
                    }
                }
            }
        }
        List<List<Integer>> r = new ArrayList<>();
        r.addAll(res.values());
        return r;
    }



    @Test
    public void test() {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> lists = threeSum2(nums);
        log.info("this is test");
    }
}
